#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 1e5+10;
const int mod = 100003;

ll f[N];
int n,k,a[N],tot;

ll qp(ll x,int t){ll res=1;for(;t;t>>=1,x=x*x%mod) if(t&1)res = res * x % mod;return res;}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,k = in;
	for(int i = 1;i <= n;i++) a[i] = in;
	f[n + 1] = 0;
	for(int i = n;i >= 0;i--) f[i] = (f[i + 1] * (n - i) % mod + n) * qp(i,mod-2) % mod;
	for(int i = n;i >= 1;i--){
		if(a[i] == 0) continue;
		tot++;
		for(int j = 1;j * j <= i;j++){
			if(i % j == 0){
				a[j] ^= 1;
				if(j * j != i) a[i / j] ^= 1;
			}
		}
	}
	ll ans = 0;
	if(tot <= k) ans = tot;
	else{
		for(int i = tot;i > k;i--) ans += f[i],ans %= mod;
		ans += k; ans %= mod;
	}
	for(int i = 2;i <= n;i++) ans = ans * i % mod;
	printf("%lld\n",ans);
	return 0;
}

